package common;

import java.util.ArrayList;
import java.util.List;

import model.TableInfo;

public class SplitArray {
	/*
	 * 将数组分成两个和最接近的数组，分解的数组的长度不定 给定一个数组，[2,5,2,1,4] sum_2 =
	 * sum(array)/2,也就是用sum_2的体积去装array 中的物品，使其最大
	 */
	
	private int[][] model = new int[0][0];
	private List<List<TableInfo>> result = new ArrayList<List<TableInfo>>();
	
	public SplitArray execute(List<TableInfo> array, int n) {
		int sum_2 = 0;
		int len = array.size();
		for (int i = 1; i < len; i++)
			sum_2 += Math.round(getProperMemory(array.get(i)));
		sum_2 = sum_2/n;
		System.out.println("sum_2=" + sum_2);
		model = new int[sum_2 + 10][sum_2 + 10];
		for (int i = 1; i < len; i++) {
			for (int j = 0; j <= sum_2; j++) {
				int memory =  Math.round(getProperMemory(array.get(i)));
				if (j >= memory) {
					model[i][j] = Math.max(model[i - 1][j], model[i - 1][j - memory] + memory);
				} else
					model[i][j] = model[i - 1][j];
			}
		}
		int j = sum_2;
		List<TableInfo> numbers = new ArrayList<TableInfo>();
		for (int i = len - 1; i > 0; i--) {
			if (model[i][j] > model[i - 1][j]) { // 找到第一个接近 sum/2 的，然后与
													// 它上面的比较，如果大于，则代表当前 i 被选中
				System.out.print(array.get(i).getMemory() + " ");
				numbers.add(array.get(i));
				j -= Math.round(getProperMemory(array.get(i)));
			}
		}
		result.add(numbers);
		n=n-1;
		if(n>0) {
			for(int k=0; k<numbers.size();k++){
				array.remove(numbers.get(k));
			}
			execute(array, n);
		} else {
			for (int p = 0; p < result.size(); p++) {
				if (result.get(p).size() == 0) {
					result.remove(p);
					List<TableInfo> first = result.remove(0);
					execute(first, 2);
				}
			}
		}
		
		return this;
	}
	
	private float getProperMemory(TableInfo tableInfo) {
		float memory = Float.parseFloat(tableInfo.getMemory());
		if (memory < 1) {
			memory = 1.0f;
		}
		return memory;
	}
	
	public List<List<TableInfo>> getResult() {
		return result;
	}

	public static void main(String args[]) {
		List<TableInfo> array = new ArrayList<TableInfo>();
		TableInfo tableInfo = null;
		
		tableInfo = new TableInfo();
		tableInfo.setMemory("144");
		array.add(tableInfo);
		
		tableInfo = new TableInfo();
		tableInfo.setMemory("28");
		array.add(tableInfo);
		
		List<TableInfo> sources = new ArrayList<TableInfo>(array);
		
		tableInfo = new TableInfo();
		tableInfo.setMemory("0");
		sources.add(0, tableInfo);
		
//		
//		tableInfo = new TableInfo();
//		tableInfo.setMemory("2");
//		array.add(tableInfo);
		
//		tableInfo = new TableInfo();
//		tableInfo.setMemory("200");
//		array.add(tableInfo);
//		
//		tableInfo = new TableInfo();
//		tableInfo.setMemory("100");
//		array.add(tableInfo);
//		
//		tableInfo = new TableInfo();
//		tableInfo.setMemory("625");
//		array.add(tableInfo);
//		
//		tableInfo = new TableInfo();
//		tableInfo.setMemory("0.0625");
//		array.add(tableInfo);
		SplitArray spliter = new SplitArray().execute(sources, 2);
		System.out.println(spliter.getResult().toString());

	}
}
